package algs4.ds;

import java.util.Iterator;
import java.util.NoSuchElementException;

public class LinkedStack<E> extends Stack<E>
{
    /* Inner Class */
    private class ListIterator implements Iterator<E>
    {
        private Node<E> link = head;

        public boolean hasNext() { return link != null;                         }
        public E       next()    { E e = link.data; link = link.next; return e; }
    }

    /* Fields */
    private Node<E> head;
    private int     size;

    /* Constructors */
    public LinkedStack() { head = null; size = 0; }

    /* Instance methods */
    public boolean     isEmpty()  { return head == null;       }
    public int         size()     { return size;               }
    public Iterator<E> iterator() { return new ListIterator(); }

    public void push(E e) {
        // update
        head = new Node(e, head);
        size++;
    }

    public E pop() throws NoSuchElementException {
        // if stack is empty throw exception
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");

        // retrieve element
        E e = head.data;

        // update
        head = head.next;
        size--;

        return e;
    }

    public E peek() throws NoSuchElementException {
        // if stack is empty, then throw exception
        if (isEmpty()) throw new NoSuchElementException("Stack underflow");

        return head.data;
    }

    /* Main Test */
    public static void main(String[] args) {
        Stack<Integer> stack = new LinkedStack<>();

        for (int i = 1; i < 100; i++) {
            if (i % 3 == 0) stack.pop();
            else            stack.push(i);
        }

        for (int i : stack)
            System.out.print(i + " ");
        System.out.println();
        System.out.println("size = " + stack.size());
    }
}
